#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <error.h>

#include "heap.h"

struct HeapStruct {
	int cap;
	int size;
	ELementType* list;
};

int isFull(PQueue pq) {
	if (pq == NULL ) perror("NULL pq");
	return pq->cap == pq->size;
}

int isEmpty(PQueue pq) {
	if (pq == NULL ) perror("NULL pq");
	return pq->size == 0;
}

void insert(PQueue pq, ELementType x) {
	if (pq == NULL ) perror("NULL pq");
	if (isFull(pq)) perror("insert to full pq");

	int i = ++pq->size;
	for (; x < pq->list[i / 2]; i /= 2 ) {
		pq->list[i] = pq->list[i / 2];
	}
	pq->list[i] = x;
}

ELementType deleteMin(PQueue pq) {
	if (pq == NULL ) perror("NULL pq");
	if (isEmpty(pq)) perror("delete empty pq");

	ELementType lastElement = pq->list[pq->size];
	ELementType minElement = pq->list[1];
	pq->size --;

	int i = 1;
	while (i * 2 < pq->size) {
		// left
		if (pq->list[2 * i] < pq->list[2 * i + 1]) {
			pq->list[i] = pq->list[2 * i];
			i = i * 2;
		} else {
			pq->list[i] = pq->list[2 * i + 1];
			i = i * 2 + 1;
		}
	}
	pq->list[i] = lastElement;
	return minElement;
}

PQueue init(int capacity) {
	PQueue pq = (PQueue)malloc(sizeof(struct HeapStruct));
	if (pq == NULL) perror("out of space");
	pq->cap = capacity;
	pq->size = 0;
	// list[0] not use
	pq->list  = malloc(sizeof(ELementType) * (capacity + 1));
	if (pq->list == NULL) perror("out of space");
	return pq;
}

void printPQ(PQueue pq) {

}